The invention relates to a memory address translation unit designed to generate a mapping to translate a logical address of a data element of a data-block, to a physical address of a data cell of a data-unit, being part of a memory device, comprising an analyzer for analyzing properties of the memory device and properties of data-blocks, and a mapping generator for generating the mapping based on output of the analyzer.
The invention further relates to an image processing apparatus comprising such a memory address translation unit.
The invention further relates to a method to generate a mapping to translate a logical address of a data element of a data-block, to a physical address of a data cell of a data-unit, being part of a memory device, comprising a first step to analyze properties of the memory device and properties of data-blocks, and a second step to generate the mapping based on results of the first step.
One type of prior art memory address translation unit is disclosed in the article Array Address Translation for SDRAM-based Video Processing Application, in Visual Communications and Image Processing 2000, Proceedings of SPIE- The International Society for Optical Engineering, Vol. 4067, part two, Year 2000, pages 922.931.
As the resolution of video processing applications becomes high, video signal processors have to deal with a large amount of data within a tightly bounded time. To obtain high memory bandwidth, some memory devices, e.g. SDRAM, use an important feature: the burst access mode. The burst access mode makes it possible to access a number of consecutive data words by giving one read or write command. Because the reading of dynamic memory cells is destructive, the content in a row of cells in the memory bank is copied into a row of static memory cells, the page registers. Subsequently, access to this row is provided. Similarly, when another row has to be accessed, first the content in the row of static memory cells has to be copied back into the original, destructed, dynamic cells. These actions, referred to as row-activations and respectively pre-charges, consume valuable time in which the array of memory cells, i.e. a bank, cannot be accessed. To optimize the utilization of the memory-bus bandwidth, data should only be accessed at the grain size of a data burst, e.g. eight words. These data bursts represent non-overlapping data-units in the memory device which can only be accessed as a whole. Because a request for data may concern only a few bytes, i.e. the data-units are larger than the requested data blocks and a request for data can involve more than one data-unit in the memory device, the amount of transfer overhead may be significant. To minimize this overhead a good mapping from logical addresses to physical addresses is important. To illustrate this the following example is provided. A video processing algorithm processes two-dimensional arrays of 8xc3x978 pixels. Such two-dimensional arrays are represented as data-blocks. If the addresses of the various pixels are linearly mapped to physical addresses, accessing such a data-block causes seven row-changes. However if the pixels of such 8xc3x978 data-block are kept in one data-unit of the memory device, accessing such a 8xc3x978 data-block does not induce any row-changes.
From the article Array Address Translation for SDRAM-based Video Processing Application, in Visual Communications and Image Processing 2000, Proceedings of SPE- The International Society for Optical Engineering, Vol. 4067, part two, Year 2000, pages 922-931, is known a memory address translation unit for reducing the number of memory cycles in multi-dimensional video processing applications. In this article an algorithm is described that searches for a suitable window size considering the memory access patterns and memory parameters. A logical array, e.g. a video frame, is partitioned into a set of rectangles called windows. The window size determines how pixels from e.g. a video frame are divided into a number of groups of related pixels. In other words, a video frame is split in a number of regions, wherein the spatial dimensions of such a region correspond to the dimensions of a window. All pixels from such a region belong to one group of related pixels. Each group of related pixels is stored in a row of the memory device. The length of a window corresponds with the number of pixels in horizontal direction. The height of a window corresponds with the number of pixels in vertical direction. Address translation means determination of a physical address for a logical address. To store a data element into a memory device, a physical address of a data-cell, being a part of a data-unit, has to be calculated for the logical address of the data element. Each pixel has a logical address. This address might be the set of co-ordinates of the pixel within the video frame. If it is required that a group of related pixels has to be stored in one data-unit, then this determines the calculation of the physical addresses related to the pixels to be stored. The pixels from a group of related pixels should be mapped to consecutive physical addresses. In the article a mapping of video data into memory is proposed related to analyzing the application software.
The consequences of estimating the window size by analyzing the application software only, is that the estimated window size is not optimal. This results in a mapping of logical to physical addresses that is not optimal. The effect is that a group of related pixels is not stored in one data-unit but spread over several data-units. One data-block request, to access such a group of related pixels has a significant memory transfer overhead. The memory device is invoked several times, instead of performing one burst access.
Besides the consequence of estimating the window size by analyzing the application software only, without considering data dependencies, it is not always possible to analyze the application software, because the code might not be available. That may be an issue if the code, or parts of it, has been developed by a third party.
It is a first object of the invention to provide a memory address translation unit of the kind described in the opening paragraph with an improved mapping to translate a logical address of a data element of a data-block to a physical address of a data cell of a data-unit.
It is a second object of the invention to provide an image processing apparatus comprising such a memory address translation unit.
It is a third object of the invention to provide a method of the kind described in the opening paragraph with improved mapping to translate a logical address of a data element of a data-block to a physical address of a data cell of a data-unit.
The first object of the invention is achieved in that the analyzer analyzes values of properties of actual data-blocks that are actually stored to or retrieved from the memory device during a predetermined period of time. Values of properties of data-blocks that are actually stored or retrieved runtime, can differ from values of properties of data-blocks from which it is assumed, based on analysis of the application software only, that they will be stored or retrieved. Furthermore the probability of occurrence of the data-blocks is impossible to derive by analyzing the application software, without considering data dependencies. Most application programs contain a number of loops and conditional tests. The consequence of these conditional tests is that the program has a number of parallel paths. The input data of the program determines which paths are actually taken. In other words the input data to be processed by an application program strongly influences the internal variables of the program and thus the memory accesses. This happens for example in an MPEG decoder. It strongly depends on the strategy taken by the encoder what type of data-blocks the MPEG decoder will have as its operands.
An embodiment of the memory address translation unit according to the invention is described in claim 2. An important property of the data-blocks is the probability distribution of the physical address of each first data cell corresponding to the first data element of each data-block that is actually stored to or retrieved from the memory device. Based on such address, the size of a data-unit and the size of the particular data-block it can be determined how many data-units contain data elements from that data-block. If the number of data elements of one data-block fit in one data-unit it is favorable that they are placed in one data-unit. Spread of data elements over data-units must be as minimal as possible. Because if a request for data overlays more than one data-unit in the memory device, then each of the data-units must be accessed resulting in a significant memory transfer overhead.
An embodiment of the memory address translation unit according to the invention is described in claim 3. Another important property of the data-blocks is the probability of occurrence. A program can have several types of operands corresponding to types of data-blocks. For example in the case of MPEG the set of data-blocks is V=(16xc3x9716), (17xc3x9716), (16xc3x9717), (17xc3x9717), (16xc3x978), (18xc3x978), (16xc3x979), (18xc3x979) (16xc3x974), (18xc3x974), (16xc3x975), (18xc3x975). However these types are not all used with the same frequency. The probability of occurrence and thus request for memory access differs per type. For MPEG applications, the reference pictures are written in memory by means of MacroBlocks. Although the amount of write requests is equal, the probability of occurrence is relative to the total amount of request. Hence, the occurrence probability of the write requests highly depends on the amount of data requests for the prediction. The latter, is determined by amongst others, the amount of field and frame predictions, the structure of the Group Of Pictures (GOP), the amount of forward, backward and bi-directional predicted MacroBlocks in a B-picture, etc. It is advantageous if the mapping depends on the probability of occurrence. If the probability of occurrence of a specific type of data-block is relatively high, then it must have a relatively high influence on the window size.
An embodiment of the memory address translation unit according to the invention is described in claim 4. Based on the information gathered by inspecting all memory accesses during a predetermined period of time, the memory translation unit is arranged to analyze whether the current mapping, as used during the predetermined period of time, resulted in the lowest possible memory transfer overhead for the data-blocks stored in respectively retrieved from the memory device. Besides information about the data-blocks which is achieved by inspecting all memory accesses during a predetermined period of time, values of properties of the memory device must be known, e.g. the width of the memory bus and the number of banks. These properties are constants and must be provided to the memory address translation unit. With a cost function of the memory transfer overhead the optimal dimensions of the windows can be calculated mathematically. The mapping is primarily based on the dimensions of the windows.
An embodiment of the memory address translation unit according to the invention is described in claim 5. The memory address translation unit is arranged to create a new mapping when it is externally triggered to do so. The advantage is that the external trigger can be invoked at any time.
An embodiment of the memory address translation unit according to the invention is described in claim 6. The memory address translation unit is arranged to create a number of mappings. For each of these mappings the memory address translation unit is able to calculate the memory transfer overhead One of these mappings is the one that is actually in use, i.e. the active mapping. If the memory address translation unit detects that the active mapping did not result in the lowest possible memory transfer overhead, then the mapping with the lowest possible memory transfer overhead can be made the active mapping. The result of this strategy is that at any time the chance that the active mapping is equal to the mapping with the lowest possible memory transfer overhead is relatively high.
An embodiment of the memory address translation unit according to the invention is described in claim 7. The memory address translation unit is beneficial in all cases that use is made of a memory device having the feature of burst access mode. The burst access mode makes it possible to access a number of consecutive data words by giving one read or write command. An example of such memory device is a synchronous dynamic random access memory (SDRAM) device. Also for accessing more sophisticated memory devices like double data rate synchronous DRAM (DDR SDRAM) or Direct Rambus DRAM the memory address translation unit is beneficial.
An embodiment of the memory address translation unit according to the invention is described in claim 8. Most video processing algorithms are based on multi-dimensional arrays, i.e. data-blocks and nested loops. Usage of the memory address translation unit can be very beneficial for video or still-image processing algorithms. In that case an element of a data-block is related to the luminance value of a pixel. The luminance value of a pixel may represent the value of the combination of color components, Red Green and Blue, or the value of one of the color components.
An embodiment of the memory address translation unit according to the invention is described in claim 9. Besides the feature of the burst access mode, memory devices can have a multiple bank architecture. To hide the memory cycles needed for row-activations and pre-charges, a multiple bank architecture is used, where each bank is accessed alternatively. A bank is accessed independently from the other banks. The organization into memory banks, i.e. a strategy to spread the data-blocks over the various banks, is an important element for memory bandwidth efficiency. This strategy must be provided to the memory address translation unit. Knowledge of the meaning of the data-blocks is important. For several applications in a multi-media system, it is necessary to read the video data both progressively and interlaced, e.g. frame prediction and field prediction for MPEG decoding. However, when subsequent odd and even lines are mapped onto the same data-unit, it is not possible to access only odd or even lines without wasting memory bandwidth. Therefore, the odd and even lines are positioned in different banks of the memory device. As a result, the data-units are interleaved in the memory device when the vertical size of the data-blocks is larger than 1. This knowledge must be taken into account in order to determine the optimal mapping. To achieve this, the set of data-blocks used to determine the optimal mapping must consist of data-blocks belonging to data request of:
both progressive and interlaced video, or
interlaced video only, or
progressive video only
This means that the set of data-blocks comprises:
data-blocks for which a data element of a data-block is related to the luminance value of a pixel belonging to an even line of a video frame;
data-blocks for which a data element of a data-block is related to the luminance value of a pixel belonging to an odd line of a video frame; and
data-blocks for which a data element of a data-block is related to the luminance value of a pixel belonging to an even line or an odd line of a video frame.
An embodiment of the memory address translation unit according to the invention is described in claim 10. In many cases data-blocks will be requested, wherein all rows of the data-block have equal numbers of data elements. In that case all data elements of the rectangular data-block are accessed. It might be that retrieval of all data elements of this rectangular data-block is not required, e.g. because some of these data elements have been accessed already. The memory address translation unit is able to generate a mapping by analyzing data-blocks of both types.
The third object of the invention is achieved in that the method comprises a first step to analyze values of properties of the data-blocks that are actually stored to or retrieved from the memory device during a predetermined period of time and a second step to generate the mapping.